The present invention pertains generally to the field of computer hardware. More specifically, the present invention pertains to a method and apparatus for resolving priorities among a number of data values.
In a computer network, data are typically transferred in data structures referred to as xe2x80x9cpackets.xe2x80x9d A packet can travel through network according to information included within the packet header. Network routers and switches can receive packets, and process the packet according to the header information. Typical routers and switches carry out the packet routing and switching functions by a matching the header (or portions of the header) to a number of entries. If the header matches an entry, an indication (e.g., a MATCH signal) will be generated. The match indication can be used by the routers and switches to determine the packet""s destination and the manner to which the packet should be processed.
One type of device that is particularly useful for performing the xe2x80x9cmatchingxe2x80x9d function is the content addressable memory (CAM). The main advantage of a CAM device is that the entire CAM can be searched in a single clock cycle. The input signal to the CAM would be a bit string representation of the data being searched for in the CAM. The outputs would be a MATCH signal indicating whether the data are found, and the address of the CAM where the matching data is located. If matching data is found in multiple addresses the CAM may also generate priority data indicative of the relative importance and priority of the addresses.
Given a large number of addresses, each having an assigned priority, the determination of which of those addresses has the highest priority is difficult.
According to one embodiment, the larger the data value, the higher the priority. Thus, the largest data value corresponds to the highest priority value.
The brute force approach is to compare address priorities two at a time. For a thousand possible priority values, the first step would require five hundred comparators. The lower priority value of each pair would be tossed aside, and the higher priority value would be passed on to the next step. This shrinking cone of comparators would continue until the highest priority address is left. This method, while straightforward, requires an increasingly large number of comparators as the number of address priorities to be compared increases.
In summary, a method and apparatus for resolving priority among a plurality of data values is disclosed. The priority resolution method of the present invention does not compare the data values two at a time. Furthermore, the priority resolution method of the present invention does not require an increasingly large number of comparators as the number of data values to be compared increases.
The priority resolution method of the invention analyzes the data values one bit-position at a time, starting from the most significant bit. For each bit-position, the method determines whether any one of the bits at the current bit-position is asserted (e.g., the bit has a value of xe2x80x9c1xe2x80x9d). If at least one of the is asserted, the data values associated with the unasserted bits (e.g., bits having values of xe2x80x9c0xe2x80x9d) are eliminated from consideration as the highest priority data value in the subsequent steps. If none of the bits at the current bit-position is asserted, none of the data values will be eliminated from consideration as the highest priority data value. The same steps are repeated for each successive bit until only the largest data value remains.
An embodiment of the present priority resolution method may be used to determine the smallest value among a plurality of data values. In that embodiment, the data values are first bit-wise inverted. The bit-wise inverted data values are then analyzed, one bit at a time, starting from the most significant bit, until only the largest inverted data value remains. The smallest data value is then obtained by inverting the largest inverted data value.
An apparatus in accordance with the present invention includes a circuit for resolving priorities among a plurality of data values. The circuit of the present embodiment includes a plurality of successive stages, each of which is configured for analyzing one bit-position of the data values. Each stage includes a circuit for receiving xe2x80x9cstill validxe2x80x9d bits from a previous stage, a circuit for determining whether the data bits at the bit-position are asserted, and a circuit for generating xe2x80x9cstill validxe2x80x9d bits for the next stage. In the present embodiment, the xe2x80x9cstill validxe2x80x9d bits indicate that the associated data values are still valid. That is, if a data value""s xe2x80x9cstill validxe2x80x9d bit is asserted, then it can be determined that the data value has not been eliminated for consideration as the highest priority data value by a previous stage. Data values are eliminated from consideration one stage at a time until the largest data value is left.
Embodiments of the present invention include the above and further include a circuit for resolving highest priority amongst a plurality of data values. The circuit includes: a first stage for receiving the first highest priority bits of the data values, and a second stage for receiving the second-from-highest priority bits. Particularly, the first stage includes circuitry for determining whether the first highest priority bits of the data values are asserted, and circuitry for generating xe2x80x9cstill validxe2x80x9d signals associated with the data values having asserted highest priority bits. The second stage receives the xe2x80x9cstill validxe2x80x9d bits generated by the first stage, and includes circuitry for determining whether the second-from-highest priority bits of the data values associated with the xe2x80x9cstill validxe2x80x9d signals are asserted. The second stage also has circuitry for generating xe2x80x9cstill validxe2x80x9d signals associated with the data values not eliminated by the first stage and having asserted second-from-highest priority bits. The xe2x80x9cstill validxe2x80x9d signals are then used by a subsequent stage to further eliminate data values from consideration.